

class Solution:

    def partition(self, s):

        n = len(s)
        ans = []
        path = []

        def dfs(i, start):

            if i == n:
                ans.append(path.copy())
                return
            

            if i < n - 1:
                dfs(i + 1, start)
            
            # 分割的情况
            t = s[start: i + 1]
            if t == t[::-1]:
                path.append(t)
                # 如果前面子串是回文，递归处理后续部分
                dfs(i + 1, i + 1)
                path.pop()

        
        dfs(0, 0)
        return ans



